/*
Date:20210504 12:54PM
key:回溯法 有路就不断深入 如果有路但又是访问过则有环 不成立46/49
*/
class Solution {
public:
    bool judge(const int & point,const vector<vector<int>>&mat,bool*& vis)
    {
        //以point为点出发
        vis[point]=1;
        //cout<<point<<" ";
        for(int i=0;i<mat.size();i++)
        {
            //有路情况下，两种可能
            if(mat[point][i]==1)
            {
                if(vis[i]==1){return 0;}
                else
                {

                    if(!judge(i,mat,vis)){return 0;};
                    vis[i]=0;
                }
                

            }
        }
        return 1;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        //建立距离矩阵
        vector<vector<int>>mat;
        mat.resize(numCourses);
        for(int i=0;i<numCourses;i++){mat[i].resize(numCourses);}
        for(int i=0;i<numCourses;i++)
        {
            for(int j=0;j<numCourses;j++)
            {
                mat[i][j]=0;
            }
        }
        //填入路
        bool*vis=new bool[numCourses];
        memset(vis,false,numCourses);
        
        for(vector<int>v:prerequisites)
        {
            
            mat[v[1]][v[0]]=1;
        }
        //dfs以每一个点为出发点判断有无环
        for(int i=0;i<numCourses;i++)
        {
            if(judge(i,mat,vis)==false){return 0;}
            //cout<<"\n";
            vis[i]=0;
        }
        return 1;
    }
};